package com.example.temp;

public class Test15 {

    public static void main(String[] args) {

    }

    /**
     *  输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
     */

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Solution {
        public ListNode Merge(ListNode list1, ListNode list2) {

            if (list1 == null) return list2;
            if (list2 == null) return list1;

            //创建虚拟头结点
            ListNode dummyHead = new ListNode(0);
            ListNode cur = dummyHead;
            while (list1 != null && list2 != null) {
                //1、虚拟头结点指向较小数、
                //2、cur指针指向list1
                //3、list1指向list1.next
                if (list1.val < list2.val) {
                    cur.next = list1;
                    cur = list1;
                    list1 = list1.next;
                } else {
                    cur = cur.next = list2;
                    list2 = list2.next;
                }
            }

            if (list1 == null) {
                cur.next = list2;
            }
            if (list2 == null) {
                cur.next = list1;
            }

            return dummyHead.next;
        }

        public ListNode MergeDigui(ListNode list1, ListNode list2) {

            if (list1 == null) return list2;
            if (list2 == null) return list1;


            if (list1.val <= list2.val) {
                list1.next = MergeDigui(list1.next, list2);
                return list1;
            } else {
                list2.next = MergeDigui(list1, list2.next);
                return list2;
            }

        }
    }
}
